from typing import List
from collections import deque


class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        inf = 201
        n = len(grid)
        d = [[inf for _ in range(n)] for _ in range(n)]
        q = deque()
        for row in range(n):
            for col in range(n):
                if grid[row][col]:
                    d[row][col] = 0
                    q.append([row, col])

        if not q or len(q) == n * n:
            return -1

        while q:
            row1, col1 = q.popleft()
            empty = (not q)
            for row2, col2 in [(row1-1, col1), (row1+1, col1), (row1, col1-1), (row1, col1+1)]:
                if 0 <= row2 < n and 0 <= col2 < n and d[row2][col2] == inf:
                    d[row2][col2] = d[row1][col1] + 1
                    q.append([row2, col2])
            if empty and (not q):
                return d[row1][col1]


grid = [[1,0,1],[0,0,0],[1,0,1]]
print(Solution().maxDistance(grid))

grid = [[1,0,0],[0,0,0],[0,0,0]]
print(Solution().maxDistance(grid))